package Bit排序算法;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Random;

/**关注一下所有排序如何改为降序！！！！！！！！！！！
 * @author zx
 * @create 2022-03-15 23:40
 */
public class SevenSort {
    /**
     * 借助栈来实现非递归分治快排
     * @param arr 看看思路就行,当时测试估计内部那个方法调错了,懒得排了
     */
    public static void quickSortNonRecursion(int[] arr) {
        Random rnd = new Random();
        Deque<Integer> stack = new ArrayDeque<>();
        // 栈中保存当前集合的开始位置和终止位置
        int l = 0;
        int r = arr.length - 1;
        stack.push(r);
        stack.push(l);
        while (!stack.isEmpty()) {
            // 栈不为空时，说明子区间还没有处理完毕
            int left = stack.pop();
            int right = stack.pop();
            if (left >= right) {
                // 区间只有一个元素
                continue;
            }
            //生成[l,r]之间的随机索引
            int p = l + rnd.nextInt(r - l + 1);
            // 依次将右区间的开始和结束位置入栈
            stack.push(right);
            stack.push(p + 1);
            // 再将左侧区间的开始和结束位置入栈
            stack.push(p - 1);
            stack.push(left);
        }
    }


    /**
     * @param arr 三路快排
     */
    public static void quickSort3(int[] arr) {
        Random rnd = new Random();
        partition3(arr,0,arr.length - 1,rnd);
    }
    private static void partition3(int[] arr, int l, int r,Random rnd) {
        if (r - l <= 15) {
            insertionSort(arr,l,r);
            return;
        }
        //生成[l,r]之间的随机索引
        int p = l + rnd.nextInt(r - l + 1);
        swap(arr,l,p);
        int v = arr[l];
        // 这些变量的取值，一定是满足区间的定义，最开始的时候，所有区间都是空
        // arr[l + 1..lt] < v
        // lt是指向最后一个<v的元素
        int lt = l;
        // arr[lt + 1..i) == v
        // i - 1是最后一个 = v的元素
        int i = lt + 1;
        // arr[gt..r] > v
        // gt是第一个 > v的元素
        int gt = r + 1;
        // i从前向后扫描和gt重合时，所有元素就处理完毕
        while (i < gt) {
            if (arr[i] < v) {
                // arr[l + 1..lt] < v
                // arr[lt + 1..i) == v
                swap(arr,i,lt + 1);
                i ++;
                lt ++;
            }else if (arr[i] > v) {
                // 交换到gt - 1
                swap(arr,i,gt - 1);
                gt --;
                // 此处i不++，交换来的gt - 1还没有处理
            }else {
                // 此时arr[i] = v
                i ++;
            }
        }
        // lt落在最后一个 < v的索引处
        swap(arr,l,lt);
        // arr[l..lt - 1] < v
        partition3(arr,l,lt - 1,rnd);
        // arr[gt..r] > v
        partition3(arr,gt,r,rnd);
    }


    //看二路快排
    /**
     * @param arr 二路快排
     */
    public static void quickSort2(int[] arr) {
        Random rnd = new Random();
        quickSortInternal2(arr,0,arr.length - 1,rnd);
    }
    private static void quickSortInternal2(int[] arr, int l, int r,Random rnd) {
        if (r - l <= 15) {
            insertionSort(arr,l,r);
            return;
        }
        int p = partition2(arr,l,r,rnd);
        quickSortInternal2(arr,l,p - 1,rnd);
        quickSortInternal2(arr,p + 1,r,rnd);
    }
    /**
     * 二路快排的分区
     * 在arr[l..r]上进行分区处理
     * @return
     */
    private static int partition2(int[] arr, int l, int r,Random rnd) {
        //生成[l,r]之间的随机索引
        int p = l + rnd.nextInt(r - l + 1);
        swap(arr,l,p);
        // arr[l + 1..i) <= v
        // [l + 1..l + 1) = 0
        int i = l + 1;
        // arr(j..r] >= v
        // (r...r] = 0
        int j = r;
        int v = arr[l];
        while (true) {
            // i从前向后扫描，碰到第一个 >= v的元素停止
            while (i <= j && arr[i] < v) {
                i ++;
            }
            // j从后向前扫描，碰到第一个 <= v的元素停止
            while (i <= j && arr[j] > v) {
                j --;
            }
            if (i >= j) {
                break;
            }
            swap(arr,i,j);
            i ++;
            j --;
        }
        // j落在最后一个 <= v的元素身上
        swap(arr,l,j);
        return j;
    }



    /**
     * @param arr 快排版本一：加入随机化选取基准
     * 快速排序是否是一个稳定性的排序算法？
     * 现在已有的所有分区函数的设计中，还没有一个能保证稳定性的算法。
     * 快排时间复杂度分析：logN就是递归函数的调用次数；n是partition
     */
    public static void quickSort(int[] arr) {
        Random rnd = new Random();
        quickSortInternal(arr,0,arr.length - 1,rnd);
    }
    /**
     * 在arr[l..r]上进行快速排序
     */
    private static void quickSortInternal(int[] arr, int l, int r,Random rnd) {
        if (r - l <= 15) {
            insertionSort(arr,l,r);
            return;
        }
        // 先获取分区点
        // 所谓的分区点就是经过分区函数后，某个元素落在了最终的位置
        // 分区点左侧全都是小于该元素的区间，分区点右侧全都是 >= 该元素的区间
        int p = partition(arr,l,r,rnd);
        // 重复在左区间和右区间上重复上述流程
        quickSortInternal(arr,l,p - 1,rnd);
        quickSortInternal(arr,p + 1,r,rnd);
    }
    /**
     * 在arr[l..r]上的分区函数，返回分区点的索引
     */
    private static int partition(int[] arr, int l, int r,Random rnd) {
        //生成[l,r]之间的随机索引
        int p = l + rnd.nextInt(r - l + 1);
        swap(arr,l,p);
        int v = arr[l];
        // arr[l + 1..j] < v
        // arr[j + 1..i) >= v
        // i表示当前正在扫描的元素
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < v) {
                swap(arr,j + 1,i);
                j ++;
            }
        }
        // 将基准值和最后一个 < v的元素交换，基准值就落在了最终位置
        swap(arr,l,j);
        return j;
    }


    public static void mergeSort(int[] arr) {
        mergeSortInternal(arr,0,arr.length - 1);
    }
    /**
     * 在arr[l,r]进行归并排序,整个arr经过此函数后就是一个已经有序的数组
     * 时间复杂度分析：
     * 递归的深度就是拆分数组所用的时间，就是树的高度（logN）
     * 合并两个子数组的过程merge；就是一个数组的遍历过程：O(n)
     * 归并排序是一个稳定的nlogn排序算法
     * 此处的稳定指的是时间复杂度稳定且归并排序也是一个稳定性排序算法
     * 时间复杂度稳定：无论集合中的元素如何变化，归并排序的时间复杂度一直都是nlogn,不会退化为O(n^2)
     *
     * 归并排序的两点优化：
     * 1.当左右两个子区间走完子函数后，左右两个区间已经有序了；如果此时arr[mid] < arr[mid + 1]
     * arr[mid]已经是左区间的最大值；arr[mid + 1]已经是右区间的最小值 => 整个区间已经有序了，没必要再执行merge过程
     * 2.在小区间上，可以直接俄使用插入排序来优化，没必要元素一致拆分到1位置
     * r - l <= 15,使用插入排序性能是很好的。可以减少归并的递归次数
     */
    private static void mergeSortInternal(int[] arr, int l, int r) {
        if (r - l <= 15) {
            // 优化2.小区间直接使用插入排序
            insertionSort(arr,l,r);
            return;
        }
        int mid = l + ((r - l) >> 1);
        // 将原数组拆分为左右两个小区间，分别递归进行归并排序
        // 走完这个函数之后 arr[l..mid]已经有序
        mergeSortInternal(arr,l,mid);
        // 走完这个函数之后 arr[mid + 1..r]已经有序
        mergeSortInternal(arr,mid + 1,r);
        // 优化1.只有左右两个子区间还有先后顺序不同时才merge
        if (arr[mid] > arr[mid + 1]) {
            merge(arr,l,mid,r);
        }
    }
    /**
     * 合并两个子数组arr[l,mid]和arr[mid + 1,r]
     * 为一个大的有序数组arr[l,r]
     *
     为啥合并过程需要创建一个临时temp数组呢？
     防止在合并的过程中，因为小元素覆盖大的元素，丢失某些元素
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        // 先创建一个新的临时数组temp
        int[] temp = new int[r - l + 1];
        // 将arr元素值拷贝到temp上
        for (int i = 0; i < temp.length; i++) {
            temp[i] = arr[i + l];
        }
        // i就是左侧小数组的开始索引
        int i = l;
        // j就是右侧小数组的开始索引
        int j = mid + 1;
        // k表示当前正在合并的原数组的索引下标
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 左侧区间已经被处理完毕，只需要将右侧区间的值拷贝原数组即可
                arr[k] = temp[j - l];
                j ++;
            }else if (j > r) {
                // 右侧区间已经被处理完毕，只需要将左侧区间的值拷贝到原数组即可
                arr[k] = temp[i - l];
                i ++;
            }else if (temp[i - l] <= temp[j - l]) {
                // 此时左侧区间的元素值较小，相等元素放在左区间，保证稳定性！！！
                arr[k] = temp[i - l];
                i ++;
            }else {
                // 右侧区间的元素值较小
                arr[k] = temp[j - l];
                j ++;
            }
        }
    }

    /**
     * 归并排序的迭代写法(了解)
     * @param arr
     */
    public static void mergeSortNonRecursion(int[] arr) {
        // 最外层循环表示每次合并的子数组的元素个数
        for (int sz = 1; sz <= arr.length; sz += sz) {
            // 内层循环的变量i表示每次合并的开始索引
            // i + sz 就是右区间的开始索引，i + sz < arr.length说明还存在右区间
            for (int i = 0; i + sz < arr.length ; i += sz + sz) {
                //当sz不断变大时,有可能i + 2sz - 1已经超过数组的最大索引(右区间的元素个数和左区间个数不相等时)
                //此时,就是右区间的终止索引
                merge2(arr,i,i + sz - 1,Math.min(i + sz + sz - 1,arr.length - 1));

            }
        }
    }

    private static void merge2(int[] arr, int l, int mid, int r) {
        // 先创建一个新的临时数组temp
        int[] temp = new int[r - l + 1];
        // 将arr元素值拷贝到temp上
        for (int i = 0; i < temp.length; i++) {
            temp[i] = arr[i + l];
        }
        // i就是左侧小数组的开始索引
        int i = l;
        // j就是右侧小数组的开始索引
        int j = mid + 1;
        // k表示当前正在合并的原数组的索引下标
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 左侧区间已经被处理完毕，只需要将右侧区间的值拷贝原数组即可
                arr[k] = temp[j - l];
                j ++;
            }else if (j > r) {
                // 右侧区间已经被处理完毕，只需要将左侧区间的值拷贝到原数组即可
                arr[k] = temp[i - l];
                i ++;
            }else if (temp[i - l] <= temp[j - l]) {
                // 此时左侧区间的元素值较小，相等元素放在左区间，保证稳定性！！！
                arr[k] = temp[i - l];
                i ++;
            }else {
                // 右侧区间的元素值较小
                arr[k] = temp[j - l];
                j ++;
            }
        }
    }

    /**
     * @param arr 未优化的归并排序
     */
    public static void mergeSort3(int[] arr) {
        mergeSortInternal3(arr,0,arr.length - 1);
    }
    /**
     * 递归语义：在arr[l,r]进行归并排序,整个arr经过此函数后就是一个已经有序的数组
     */
    private static void mergeSortInternal3(int[] arr, int l, int r) {
        if(l >= r){//左边的索引==右边的索引
            return;
        }
        int mid = l + ((r - l) >> 1);
        // 将原数组拆分为左右两个小区间，分别递归进行归并排序
        // 走完这个函数之后 arr[l..mid]已经有序
        mergeSortInternal3(arr,l,mid);
        // 走完这个函数之后 arr[mid + 1..r]已经有序
        mergeSortInternal3(arr,mid + 1,r);
        //merge
        merge3(arr,l,mid,r);

    }
    /**
     * 合并两个子数组arr[l,mid]和arr[mid + 1,r]
     * 为一个大的有序数组arr[l,r]
     */
    private static void merge3(int[] arr, int l, int mid, int r) {
        // 先创建一个新的临时数组aux
        int[] aux = new int[r - l + 1];
        // 将arr元素值拷贝到aux上
        for (int i = 0; i < aux.length; i++) {
            aux[i] = arr[i + l];
        }
        // i就是左侧小数组的开始索引
        int i = l;
        // j就是右侧小数组的开始索引
        int j = mid + 1;
        // k表示当前正在合并的原数组的索引下标
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 左侧区间已经被处理完毕，只需要将右侧区间的值拷贝原数组即可
                arr[k] = aux[j - l];
                j ++;
            }else if (j > r) {
                // 右侧区间已经被处理完毕，只需要将左侧区间的值拷贝到原数组即可
                arr[k] = aux[i - l];
                i ++;
            }else if (aux[i - l] <= aux[j - l]) {
                // 此时左侧区间的元素值较小，相等元素放在左区间，保证稳定性
                arr[k] = aux[i - l];
                i ++;
            }else {
                // 右侧区间的元素值较小
                arr[k] = aux[j - l];
                j ++;
            }
        }
    }

    /**
     * @希尔排序
     */
    public static void shellSort(int[] arr) {
        int gap = arr.length >> 1;
        while (gap > 1) {
            //预处理阶段
            insertionSortByGap(arr,gap);
            gap = gap >> 1;
        }
        //此时gap等于1,整个集合已经接近有序,只需要全集合来一次插入排序即可
        insertionSort(arr);
    }
    //和上面的是一样的。
    public static void shellSort2(int[] arr){
        int gap = arr.length - 1;
        while (gap > 0){
            insertionSortByGap(arr,gap);
            gap = gap >> 1;
        }
    }
    /**
     * 按照gap分组进行插入排序
     * @param gap
     * 每次取一个gap,将原数组按照gap分组，组内使用插入排序
     * 直到gap = 1时，整个数组已经接近有序，最终直接插入排序一下即可。
     * （希尔排序代码）j - gap >= 0：说明前面还有距离相同的元素没有判断
     * （插入排序代码）j > 0  -->> j - 1 >= 0
     * 所以，gap == 1时，希尔排序和插入排序就是一码事！！！
     * 希尔排序算法不稳定
     */
    private static void insertionSortByGap(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            // 不断向前扫描相同gap步的元素
            // j - gap从j位置开始向前还有相同步数的元素没有判断
            for (int j = i; j  >= gap && arr[j] < arr[j - gap]; j -= gap) {//j-=gap:只看相同gap的元素
                swap(arr,j,j - gap);
            }
        }
    }

    /**
     * 在arr[l..r]使用插入排序
     * 归并优化、希尔排序、快速排序都调用了这个方法
     */
    private static void insertionSort(int[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            for (int j = i; j > l && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
            }
        }
    }

    /**
     * @param arr 直接插入排序
     * 每次从无序区间中拿第一个值插入到已经排序区间的合适位置，直到整个数组有序
     * 在近乎有序的数据测试中，插入排序的性能好
     * 极端情况下，当集合是一个(完全/近乎)有序的集合，插入排序内层循环一次都不走~~~
     * 插入排序变为O(N)；因此，插入排序经常作为高阶排序算法的优化手段之一
     * 插入排序是稳定的；arr[j] >= arr[j -  1]就停止了；相等的元素不会交换顺序，arr[j] < arr[j - 1]才交换
     */
    public static void insertionSort(int[] arr) {
        // 已排序区间[0,i)
        // 待排序区间[i...n]
        for (int i = 1; i < arr.length; i++) {
            // 待排序区间的第一个元素arr[i]
            // 从待排序区间的第一个元素向前看，找到合适的插入位置
//            for (int j = i; j > 0; j--) {
//                // arr[j - 1]已排序区间的最后一个元素
//                if (arr[j] >= arr[j - 1]) {
//                    // 相等我们也不交换，保证稳定性
//                    // 此时说明arr[j] > 已排序区间的最大值，arr[j]已经有序了~~直接下次循环
//                    break;
//                }else {
//                    swap(arr,j,j - 1);
//                }
//            }
            for (int j = i; j >= 1 && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
            }
        }
    }

    /**
     * @param arr 折半插入排序
     * 因为插入排序中，每次都是在有序区间中选择插入位置 =>> 使用二分查找来定位元素的插入位置
     */
    public static void insertionSortBS(int[] arr) {
        // 有序区间[0..i)
        // 无序区间[i...n]
        // i表示当前正在处理的元素,有序区间和无序区间的分界线就是i
        for (int i = 1; i < arr.length; i++) {
            int val = arr[i];
            int left = 0;
            int right = i;
            while (left < right){
                int mid = left + ((right - left) >> 1);
                if (val < arr[mid]) {
                    right = mid;
                }else {
                    // val >= arr[mid]
                    left = mid + 1;
                }
            }
            // 搬移left..i的元素
            for (int j = i; j > left; j--) {
                arr[j] = arr[j - 1];
            }
            // left就是val插入的位置
            arr[left] = val;
        }
    }

    /**
     * @param arr 选择排序
     */
    public static void selectionSort(int[] arr) {
        // 最开始，无序区间[0...n]  有序区间[]
        // 当无序区间只剩下一个元素时，整个集合已经有序
        for (int i = 0; i < arr.length - 1; i++) {
            // min变量存储了当前的最小值索引
            int min = i;
            // 从剩下的元素中选择最小值
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            // min这个索引一定对应了当前无序区间中找到的最小值索引，换到无序区间最前面i
            swap(arr,min,i);
        }
    }

    /**
     * 还没完全理解，再看看！！！！！！！
     * @param arr 双向选择排序
     * 一次排序过程中同时选出最大值和最小值,放在无序区间的最后和最前
     * 下去找一个此优化的动图放在优化代码里
     */
    public static void selectionSortOP(int[] arr) {
        int low = 0;
        int high = arr.length - 1;//[low,high]表示整个无序区间
        // low = high，无序区间只剩下一个元素，整个数组已经有序
        while (low <= high) {
            int min = low;
            int max = low;
            for (int i = low + 1; i <= high; i++) {
                if (arr[i] < arr[min]) {
                    min = i;
                }
                if (arr[i] > arr[max]) {
                    max = i;
                }
            }
            // min索引一定是当前无序区间的最小值索引，与low交换位置
            swap(arr,low,min);
            if (max == low) {//这个代码非常重要！！！！！！！！！！
                // 最大值已经被换到min这个位置
                max = min;
            }
            swap(arr,max,high);
            low += 1;
            high -= 1;
        }
    }

    /**
     * @param arr 冒泡排序(稳定的排序算法)
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = false;
            //第一趟排序，就是将最大的数排在最后
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j,j + 1);
                    flag = true;
                }
            }
            if (!flag) {// 在一趟排序中，一次交换都没有发生
                break;
            }
        }
    }


    /**
     * @param arr 堆排序
     * 时间复杂度 O(nlogn)
     */
    public static void heapSort(int[] arr) {
        // 1.将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
        // 从最后一个非叶子节点开始进行siftDown操作
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
            siftDown(arr,i,arr.length);
        }

        // 此时arr就被我调整为大顶堆
        // 2.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端；**********
        // 3.重新调整未调整节点，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤。
        for (int i = arr.length - 1; i > 0; i--) {
            // arr[0] 堆顶元素，就是当前堆的最大值
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }
    /**
     * 元素下沉操作
     * 调整索引为i的节点不断下沉，直到到达最终位置：
     * a.到达了叶子节点 2i + 1 >= size
     * b.当前节点值 > 左右子树的最大值(下沉到最终位置)
     ** 时间复杂度分析：
     *  时间复杂度为 O(n)
     * @param arr
     * @param i 当前要下沉的索引
     * @param length 数组长度
     */
    private static void siftDown(int[] arr, int i, int length) {
        //还存在子树(条件a)
        while (2 * i + 1 < length) {
            int j = (i * 2) + 1;
            //判断一下是否有右子树
            if (j + 1 < length && arr[j + 1] > arr[j]) {
                //此时右树存在且大于左树的值
                j = j + 1;
            }
            // j就是左右子树的最大值
            if (arr[i] > arr[j]) {//条件(b)
                // 下沉结束
                break;
            }else {
                //循环结束后，就已经将树的最大值，放在了最顶
                swap(arr,i,j);
                i = j;
            }
        }
    }

    /**
     * @param arr 交换数组中的两数
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
